package tree;

/**题目：判断一棵树是否是二叉搜索树
 * 二叉搜索树：任意节点的左节点要小于根节点，右节点要大于根节点
 * @Author Gavin
 * @date 2022.01.02 21:07
 */
public class tree_10 {
    /**
     * 第一种方法：递归
     * 我们只需要找到树的最左子树和最右子树的值，然后和根节点进行比较
     */
    //递归寻找最小值
    static TreeNode min(TreeNode root){
        while (root.left!=null)root=root.left;
        return root;
    }
    //递归寻找最大值
    static TreeNode max(TreeNode root){
        while (root.right!=null)root=root.right;
        return root;
    }
    //Time:O(n*log(n)) Space:O(n)
    public static boolean solution_1(TreeNode root){
        if(root==null)return true;
        //根节点大于左边的最大值
        boolean leftValid=root.left==null||root.val>max(root.left).val;
        //根节点小于右边的最小值
        boolean rightValid=root.right==null||root.val<min(root.right).val;
        return leftValid&&rightValid&&solution_1(root.left)&&solution_1(root.right);
    }

    /**
     * 第二种方法：每次递归的时候把需要判断大小的值带入递归函数里面
     */
    //Time:O(n),Space:O(n)
    public static boolean solution_2(TreeNode root){
        return helper(root,null,null);
    }
    public static boolean helper(TreeNode root,TreeNode lower,TreeNode upper){
        if(root==null)return true;
        if(lower!=null&&root.val<lower.val)return false;
        if(upper!=null&&root.val>upper.val)return false;
        return helper(root.left,lower,root)&&helper(root.right,root,upper);
    }
}
